package huffmancode;

import java.util.*;

public class HuffmanCode {
    public static StringBuilder stringBuilder=new StringBuilder();
    public static Map<Byte,String> map=new HashMap<>();
    public static void main(String[] args){
        String name = "lu chuan";
        Map<Byte, Integer> map = transition(name);
        List<Node> nodes = tran(map);
        Node root = huffmantree(nodes);
        Map<Byte,String> createhuffmancode = createhuffmancode(root);
        System.out.println(createhuffmancode.toString());
    }
    /*
    字符串转为byte,存入Map
     */
    public static Map<Byte,Integer> transition(String str){
        Map<Byte,Integer> map = new HashMap<>();
        byte[] bytes = str.getBytes();
        for(byte val:bytes){
            Integer count = map.get(val);
            if (count == null){
                map.put(val,1);
            }else {
                map.put(val,count+1);
            }
        }
        return map;
    }
    /*
    把map的东西转为存入Node结点
     */
    public static List<Node> tran(Map<Byte,Integer> map){
        List<Node> nodes = new ArrayList<>();
        Set<Map.Entry<Byte, Integer>> set = map.entrySet();
        for(Map.Entry<Byte, Integer> Node :set){
           nodes.add(new Node(Node.getKey(),Node.getValue()));
        }
        return nodes;
    }
    /*
        ArrayList<node>转为赫夫曼树
     */
    public static Node huffmantree(List<Node> nodes){
        while (nodes.size()>1){
            Collections.sort(nodes);
            Node left = nodes.get(0);
            Node right = nodes.get(1);
            Node newnode = new Node(left.getVal() + right.getVal());
            newnode.setLeft(left);
            newnode.setRight(right);
            nodes.add(newnode);
            nodes.remove(left);
            nodes.remove(right);
        }
        return nodes.get(0);
    }
    /*
    得到编码，左为0；右为1；
     */
    public static void code(Node root,String code,StringBuilder sb){
        stringBuilder = new StringBuilder(sb);
        stringBuilder.append(code);
        if(root!=null){
            if (root.getaByte() == null) {
                code(root.getLeft(), "0", stringBuilder);
                code(root.getRight(), "1", stringBuilder);
            }
        }
        map.put(root.getaByte(),stringBuilder.toString());
    }
    /*
    设置统一入口
     */
    public static Map<Byte,String> createhuffmancode(Node root){
        if (root==null){
            return null;
        }
        code(root.getLeft(),"0",stringBuilder);
        code(root.getRight(),"1",stringBuilder);
        return map;
    }

}
